package pathfinding.grid.astar;

import java.util.ArrayList;

import castledefense.util.Log;
import pathfinding.grid.GridLocation;
import pathfinding.grid.GridMap;
import pathfinding.grid.GridPath;
import pathfinding.grid.util.GridDouble;

public class GridAstarFlood {
	
	private final int sizeX;
	private final int sizeY;
	
	private final GridMap gridMap;
	private final GridDouble distanceMap;
	private final GridLocationAstar destination;
	
	private GridSortedLocationList sortedList;
	private boolean[][] visitedMap;
	private boolean[][] addedMap;
	
	public GridAstarFlood(GridMap map, GridLocation destination) {
		this.gridMap = map;
		this.destination = new GridLocationAstar(destination.getCellX(), 
				destination.getCellY(), true, destination.getValue(), 0, 0);
		distanceMap = new GridDouble(map.getSizeX(), map.getSizeY());
		sizeX = map.getSizeX();
		sizeY = map.getSizeY();
		generateMapDistance();
		
	}
	
	public static void main(String [] args){
		GridAstarFlood astar = new GridAstarFlood(new GridMap(201, 201), new GridLocation(200, 200, true, 1));
		while(true){
			Log.startTimerMicro();
			astar.generateMapDistance();
			int time = Log.stopTimerMicro();
			System.out.println(time);
		}
		/*astar.generateMapDistance();
		while(true){
			Log.startTimerMicro();
			astar.findPath(new GridLocation(0, 0, false, 1));
			int time = Log.stopTimerMicro();
			System.out.println(time);
		}*/
		/*astar.sortedList = new GridSortedLocationList();
		astar.visitedMap = new boolean[astar.sizeX][astar.sizeY];
		astar.distanceMap.reset(Integer.MAX_VALUE);
		astar.distanceMap.set(astar.destination.getCellX(), astar.destination.getCellY(), 0);
		astar.sortedList.add(astar.destination);
		boolean value = astar.sortedList.hasNext();
		while(value){
			
			GridLocationAstar location = astar.sortedList.getNext();
			
			if(astar.visitedMap[location.getCellX()][location.getCellY()] == true){
				continue;
			}else{
				astar.visitedMap[location.getCellX()][location.getCellY()] = true;
				//Log.startTimerMicro();
				astar.addAdjacent(location);
				//int time = Log.stopTimerMicro();
				//System.out.println(time);
			}
			value = astar.sortedList.hasNext();
			
		}*/
	}
	
	public GridPath getPath(GridLocation startLocation){
		if(gridMap.hasChanged()){
			generateMapDistance();
		}
		return findPath(startLocation);
	}
	
	private GridPath findPath(GridLocation startLocation){
		GridPath path;
		
		ArrayList<GridLocation> locationList = new ArrayList<GridLocation>();
		
		int x = startLocation.getCellX();
		int y = startLocation.getCellY();
		
		if(x == destination.getCellX() && y == destination.getCellY()){
			locationList.add(destination);
		}else{
			GridLocationAstar currentLocation = new GridLocationAstar(x, y, false, gridMap.get(x, y), 0, 0);
			locationList.add(currentLocation);
			
			while(!currentLocation.isEnd()){
				currentLocation = getSmallestAdjacent(currentLocation);
				if(currentLocation == null){
					return null;
				}
				locationList.add(currentLocation);
			}
		}
		
		path = new GridPath(locationList);
		return path;
	}
	
	private GridLocationAstar getSmallestAdjacent(GridLocationAstar previousLocation){
		int currentX = previousLocation.getCellX();
		int currentY = previousLocation.getCellY();
		
		DiagonalMove diagonal = new DiagonalMove(currentX, currentY);
		
		int x;
		int y;
		
		int smallestX = -1;
		int smallestY = -1;
		double smallestValue = distanceMap.get(currentX, currentY);
		
		//Above
		//Top left
		y = currentY + 1;
		x = currentX - 1;
		if(validLocation(x, y) && distanceMap.get(x, y) != Integer.MAX_VALUE && distanceMap.get(x, y) < smallestValue && diagonal.isValid(diagonal.top_left)){
			smallestX = x;
			smallestY = y;
			smallestValue = distanceMap.get(x, y);
		}
		//Side
		x = currentX;
		if(validLocation(x, y) && distanceMap.get(x, y) != Integer.MAX_VALUE && distanceMap.get(x, y) < smallestValue){
			smallestX = x;
			smallestY = y;
			smallestValue = distanceMap.get(x, y);
		}
		//Top right
		x = currentX + 1;
		if(validLocation(x, y) && distanceMap.get(x, y) != Integer.MAX_VALUE && distanceMap.get(x, y) < smallestValue && diagonal.isValid(diagonal.top_right)){
			smallestX = x;
			smallestY = y;
			smallestValue = distanceMap.get(x, y);
		}
		//Center
		//Side
		y = currentY;
		x = currentX - 1;
		if(validLocation(x, y) && distanceMap.get(x, y) != Integer.MAX_VALUE && distanceMap.get(x, y) < smallestValue){
			smallestX = x;
			smallestY = y;
			smallestValue = distanceMap.get(x, y);
		}
		//Side
		x = currentX + 1;
		if(validLocation(x, y) && distanceMap.get(x, y) != Integer.MAX_VALUE && distanceMap.get(x, y) < smallestValue){
			smallestX = x;
			smallestY = y;
			smallestValue = distanceMap.get(x, y);
		}
		//Under
		//Bottom left
		y = currentY - 1;
		x = currentX - 1;
		if(validLocation(x, y) && distanceMap.get(x, y) != Integer.MAX_VALUE && distanceMap.get(x, y) < smallestValue && diagonal.isValid(diagonal.bottom_left)){
			smallestX = x;
			smallestY = y;
			smallestValue = distanceMap.get(x, y);
		}
		//Side
		x = currentX;
		if(validLocation(x, y) && distanceMap.get(x, y) != Integer.MAX_VALUE && distanceMap.get(x, y) < smallestValue){
			smallestX = x;
			smallestY = y;
			smallestValue = distanceMap.get(x, y);
		}
		//Bottom right
		x = currentX + 1;
		if(validLocation(x, y) && distanceMap.get(x, y) != Integer.MAX_VALUE && distanceMap.get(x, y) < smallestValue && diagonal.isValid(diagonal.bottom_right)){
			smallestX = x;
			smallestY = y;
			smallestValue = distanceMap.get(x, y);
		}
		
		if(smallestX == -1 || smallestY == -1){
			return null;
		}
		
		GridLocationAstar newLocation = createLocation(smallestX, smallestY, previousLocation);
		
		return newLocation;
	}
	
	//------------------- GENERATE DISTANCE MAP -------------------------------
	
	private void generateMapDistance(){
		sortedList = new GridSortedLocationList();
		visitedMap = new boolean[sizeX][sizeY];
		addedMap = new boolean[sizeX][sizeY];
		distanceMap.reset(Integer.MAX_VALUE);
		sortedList.add(destination);
		addedMap[destination.getCellX()][destination.getCellY()] = true;
		distanceMap.set(destination.getCellX(), destination.getCellY(), 0);
		while(sortedList.hasNext()){
			GridLocationAstar location = sortedList.getNext();
			if(visitedMap[location.getCellX()][location.getCellY()] == true){
				continue;
			}else{
				visitedMap[location.getCellX()][location.getCellY()] = true;
				addAdjacent(location);
			}
		}
		gridMap.setHasChanged(false);
	}
	
	private void addAdjacent(GridLocationAstar previousLocation){
		int currentX = previousLocation.getCellX();
		int currentY = previousLocation.getCellY();
		
		DiagonalMove diagonal = new DiagonalMove(currentX, currentY);
		
		int x;
		int y;
		
		//Above
		//Top left
		y = currentY + 1;
		x = currentX - 1;
		if(unvisited(x, y) && diagonal.isValid(diagonal.top_left)){
			addLocation(x, y, previousLocation);
		}
		//Side
		x = currentX;
		if(unvisited(x, y)){
			addLocation(x, y, previousLocation);
		}
		//Top right
		x = currentX + 1;
		if(unvisited(x, y) && diagonal.isValid(diagonal.top_right)){
			addLocation(x, y, previousLocation);
		}
		//Center
		//Side
		y = currentY;
		x = currentX - 1;
		if(unvisited(x, y)){
			addLocation(x, y, previousLocation);
		}
		//Side
		x = currentX + 1;
		if(unvisited(x, y)){
			addLocation(x, y, previousLocation);
		}
		//Under
		//Bottom left
		y = currentY - 1;
		x = currentX - 1;
		if(unvisited(x, y) && diagonal.isValid(diagonal.bottom_left)){
			addLocation(x, y, previousLocation);
		}
		//Side
		x = currentX;
		if(unvisited(x, y)){
			addLocation(x, y, previousLocation);
		}
		//Bottom right
		x = currentX + 1;
		if(unvisited(x, y) && diagonal.isValid(diagonal.bottom_right)){
			addLocation(x, y, previousLocation);
		}
	}
	
	private GridLocationAstar createLocation(int x, int y, GridLocationAstar previousLocation){
		GridLocationAstar newLocation;
		boolean isEnd = (x == destination.getCellX() && y == destination.getCellY());
		double doneDist = previousLocation.getDoneDistance() + getDist(x, y, previousLocation.getCellX(), previousLocation.getCellY());
		double todoDist = 0;
		newLocation = new GridLocationAstar(x, y, isEnd, gridMap.get(x, y), doneDist, todoDist);
		return newLocation;
	}
	
	private void addLocation(int x, int y, GridLocationAstar previousLocation){
		GridLocationAstar location;
		
		location = createLocation(x, y, previousLocation);
		sortedList.add(location);
		double dist = Math.min(location.getDoneDistance(), distanceMap.get(x, y));
		addedMap[x][y] = true;
		distanceMap.set(x, y, dist);
	}
	
	private class DiagonalMove{

		private final int top_right = 0;
		private final int top_left = 1;
		private final int bottom_right = 2;
		private final int bottom_left = 3;
		
		private int x;
		private int y;
		
		private DiagonalMove(int x, int y){
			this.x = x;
			this.y = y;
		}

		private boolean isValid(int direction){
			//Top right
			if(validLocation(x+1, y) && validLocation(x, y+1) && direction == top_right){
				return true;
			}
			//Bottom right
			else if(validLocation(x+1, y) && validLocation(x, y-1) && direction == bottom_right){
				return true;
			}
			//Top left
			else if(validLocation(x-1, y) && validLocation(x, y+1) && direction == top_left){
				return true;
			}
			//Bottom left
			else if(validLocation(x-1, y) && validLocation(x, y-1) && direction == bottom_left){
				return true;
			}
			return false;
		}

	}
	
	private boolean isWall(int x, int y){
		return gridMap.get(x, y) == GridMap.WALL;
	}
	
	private boolean validLocation(int x, int y){
		boolean result = true;
		result &= x >= 0 && x < sizeX && y >= 0 && y < sizeY;
		if(result){
			result &= !isWall(x, y);
		}
		return result;
	}
	
	private boolean unvisited(int x, int y){
		return validLocation(x, y) && addedMap[x][y] == false;
	}
	
	private double getDist(int x, int y, int nx, int ny){
		double result = 0;
		int dx = x - nx;
		int dy = y - ny;
		result += Math.sqrt(dx*dx + dy*dy);
		result = result*0.5*gridMap.get(x, y) + result*0.5*gridMap.get(nx, ny);
		return result;
	}

}
